# 除了使用全排列剪枝的求法： 按照老师分析的例子：
"""
小莹 - 助教 | 抖码课堂:
第一题 DFS 就可以，在 DFS 的时候维护好父子关系就好，每次遍历一个节点的时候，判断这个节点是不是叶子结点的父节点

小莹 - 助教 | 抖码课堂:
第二题可以用滑动窗口，窗口大小固定为 k ，将每个窗口的字符串转成整数，取最大值即可，当然需要注意数字越界

小莹 - 助教 | 抖码课堂:
第三题，感觉可以将数组一段一段的计算，比如输入数组是 1 0 0 4 0 0 0 9 0 0 然后 k = 12 ，我们可以将数组拆成三段，
分别是 1 0 0 4 / 4 0 0 9 / 9 0 0 12（因为 12 是最大值），对于每段应该有规律可以求出填充的方案，因为数组必须保证升序

小莹 - 助教 | 抖码课堂:
比如 1 0 0 4，那么 中间两个 0 最小可以填 1 最大可以填 4 ，问题就变成了用 1 2 3 4 这 4 个数字的 2 排列了，
可以填充的方案是 1 1 / 1 2 / 1 3 / 1 4 /  2 2 / 2 3 / 2 4 / 3 3/ 3 4 / 4 4 方案数等于 4  + 3 + 2 + 1 = 10

小莹 - 助教 | 抖码课堂:
可以按照这个思路找下规律看看


# 最后一题，数组题
1 .
想了好一会，感觉， 连续0的位数 和 数字k之间没有规律~ ， 2个0的话倒是 求 k的阶层。  我觉得用暴力破解，全排列。  
求出所有的排列组合，然后剪枝， 只要符合增序的，这样效率低一些，应该可以做


2. 
当只有一个 0 时，有四种方案 4种 
当有两个 0 时， 4 3 2 1  , 10种方案（1有四种， 2有三种， 3有两种， 4有1种）
当三个0时， 10 6 3 1 ，  20种方案(1有 10种， 2有 10 - 4 = 6种，类推)
当有四个0时， 20, 10, 4, 1 ,  35种方案（1有 20种， 2有 10种。。。）

推出，每一层的 数量，可以由上一层推出！！！

假设 k = 4    1 0...0 4  , 可以填充的数字为 1 2 3 4

那么定义二维数组， 表示每个数字能构成的可能解
 1  2  3  4
[1, 1, 1, 1]    总： 4种（当中间只有一个 0， 每个数字只能构成 一个）
[4, 3, 2, 1]    总:  10  中间有两个 0
[10, 6, 3, 1]   总:  20  中间三个 0
[20, 10, 4, 1]  总:  35  中间四个 0
........

依次往下类推， 可以使用一个数组表示只有一个0的情况[1, 1, 1, 1]
便可以 迭代出 n个0 的所有可能填充！ 


黄东林:
这样看来， 空间复杂度 就是 所能选用的 数字的范围（构成1维数组）
时间复杂度： 就是连续 0的个数，假设为 n， 数字范围为 k， 则为： O(n x K)

黄东林:
求出一段的可能填充后， 总的填充可能， 应该就是 各段的填充 相乘了吧~

黄东林:
然后另外需要注意的是， 一段的 可选数字范围 是 左边界 到 min(右边界数字, k)

"""